import tool.TreeNode;
import tool.TreeNodePrint;
import tool.input;

import java.util.*;

/**
 * @Description: 二叉树的前序遍历
 * 二叉树的前序遍历
 * @Date:Create in 19:27  2022/7/14
 */
public class preorderTraversal0144 {

    public static void main(String[] args) {
        String s = "[1,null,2,null,null,3,null]";
        TreeNode root = input.getTree(s);
        TreeNodePrint.printTree(root);
        List<Integer> res = preorderTraversal2(root);

        System.out.println(res.toString());
    }

    //递归
    public static List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorder(root,result);
        return result;
    }
    public static void preorder(TreeNode root,List<Integer> result){
        if(root == null){
            return;
        }
        result.add(root.val);
        preorder(root.left,result);
        preorder(root.right,result);
    }

    //迭代1
    public static List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if(root!= null) st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.peek();
            if(node!=null){
                st.pop();// 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if(node.right!=null) st.push(node.right);// 添加右节点（空节点不入栈）
                if(node.left!=null) st.push(node.left); // 添加左节点（空节点不入栈）
                st.push(node);// 添加中节点
                st.push(null);// 中节点访问过，但是还没有处理，加入空节点做为标记。
            }else{// 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();// 将空节点弹出
                node = st.pop();// 重新取出栈中元素
                res.add(node.val);// 重新取出栈中元素
            }
        }
        return res;
    }
}
